Olivier Devillers (olivier.devillers@inria.fr)
Stefan Schirra
Design and correctness proofs of geometric algorithms usually assume exact arithmetic. Since imprecise calculations can cause wrong or, much worse, mutually contradictory decisions in the control flow of an algorithm, many implementations crash, or at best, compute garbage for some inputs. For some applications the fraction of bad inputs compared to all possible inputs is small, but for other applications this fraction is large.
Cgal has a layered design. The correctness of some components depends on the correctness of the components that are used. Correctness of a component means behaving according to its (mathematical) specification. Simply speaking, the source of the robustness problem is that the default hardware-supported arithmetic does not really fulfill the requirements of the algorithm, since it does not implement arithmetic on the real numbers.
Nevertheless, the generic implementation of the kernel primitives that are parameterized by the arithmetic (more precisely, by a number type) assumes that the arithmetic plugged in does behave as real arithmetic. The generic code does not and should not (otherwise it would slow down ``exact'' number types) deal with any potential imprecision. There are a number of (third-party provided) ``exact'' number types available for use with Cgal, where ``exact'' means that all decisions (comparison operations) are correct and that the representation of the numbers allows for refinement to an arbitrary precision, if needed. Depending of the needed computations, a suitable exact number type can be Quotient<MP_float> or gmpq if rational computations are involved. If roots of polynomials are needed, then the solution is to use leda_real provided by LEDA or CORE::Expr provided by CORE.
Cgal provides generic implementations of geometric primitives. These assume ``exact computation''. This may or may not work, depending on the actual numerical input data. Cgal also provides1 specialization of the primitives that (are still fairly generic and) guarantee exact predicate results and much higher efficiency than exact number types like arbitrary precision integers or rationals. The efficiency relies on the use of speedy floating-point arithmetic in order to filter out reliable floating-point computations. Interval arithmetic is largely used in such filter steps.
Recommendations:
1 | at present, for the dimension 2/3 Cartesian kernel(s) only. |